package leet90subsetii

import "sort"

// https://leetcode.cn/problems/subsets-ii/
func SubsetII(nums []int) [][]int {
	// 和78题不同的是，此处的nums中包含重复元素，但是结果中却不允许有重复的子集。
	// 看过之前一个解决方案，如果当前子问题的循环中选择的元素和上一个元素是一样的，就跳过，这样子集就不会重复了
	// 注意要对原集合先行排序，这样避免交叉读取的问题，一跳就全跳过去了
	sort.Ints(nums)
	result := [][]int{{}}
	path := []int{}
	var iterate func(start int)
	iterate = func(start int) {
		if start == len(nums) {
			return
		}
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue
			}
			path = append(path, nums[i])
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)

			iterate(i + 1)
			path = path[:len(path)-1]
		}
	}
	iterate(0)
	return result
}

// 示例： [4,4,4,1,4]
